package cn.edu.njust.alg;

import java.util.Arrays;
import java.util.HashMap;

public class PrimeSum {

	public static void main(String[] args) {
		long t1 = System.currentTimeMillis();
		int n = 10_0000_0000;
		// n = 30;
		System.out.println("sum: " + primeSum(n));
		//System.out.println("countPrime: " + new PrimeSum().countPrimes(5));
		System.out.println("time:" + (System.currentTimeMillis() - t1) + " ms");

	}

	/*
	 * sum: 24739512092254535 time:904 ms
	 */
	public static long primeSum(final int range) {
		int i, k;
		HashMap<Integer, Long> S = new HashMap<Integer, Long>();
		int r = (int) Math.sqrt(range);
		int p = range / r;
		int[] V = new int[r + p - 1];
		k = r + 1;
		for (i = 1; i < k; i++) {
			V[i - 1] = range / i;
		}
		int count = 1;
		for (i = r + p - 2; i >= r; i--) {
			V[i] = count++;
		}
		// ArrayUtils.printArray(V);
		for (i = 0; i < V.length; i++) {
			S.put(V[i], ((long) V[i] * (V[i] + 1) / 2 - 1));
		}
		// System.out.println(S);
		Long sp, p2;
		for (p = 2; p < r + 1; p++) {
			if (S.get(p) > S.get(p - 1)) {
				sp = S.get(p - 1);
				p2 = (long) (p * p);
				for (i = 0; i < V.length; i++) {
					if (V[i] < p2) {
						break;
					}
					S.put(V[i], S.get(V[i]) - p * (S.get(V[i] / p) - sp));
				}
			}
		}

		return S.get(range);
	}

	/*
	 *
	 */
	public int countPrimes(int n) {
		if(n<2)
			return 0;
		int count = 0;
		boolean[] primes = new boolean[n];
		primes[0] = primes[1] = true;
		int q = (int) Math.sqrt(n);
		int i, j, i2;
		j = 2;
		for (j = 2; j << 1 < n; j++) {
			primes[j << 1] = true;
		}

		for (i = 3; i <= q; i += 2) {
			if (primes[i]) {
				continue;
			}
			i2 = i * i;
			for (j = i2; j < n; j += i << 1) {
				primes[j] = true;
			}
		}
		for (i = 1; i <n; i ++) {
			if (!primes[i]) {
				count++;
			}
		}
		return count;
	}

	/*
	 * sum: 24739512092254535 time:9140 ms
	 */
	public static long primeSum_3(final int range) {
		long sum = 2;
		boolean[] primes = new boolean[range];
		// Arrays.fill(primes, true);
		primes[0] = primes[1] = false;
		int q = (int) Math.sqrt(range);
		int i, j, i2;
		j = 2;
		for (j = 2; j << 1 < range; j++) {
			primes[j << 1] = false;
		}

		for (i = 3; i <= q; i += 2) {
			if (primes[i]) {
				continue;
			}
			i2 = i * i;
			for (j = i2; j < range; j += i << 1) {
				primes[j] = true;
			}
		}
		for (i = 3; i < range; i += 2) {
			if (!primes[i]) {
				sum += i;
			}
		}
		return sum;
	}

	/*
	 * sum: 24739512092254535 time:9709 ms
	 */
	public static long primeSum_2(final int range) {
		long sum = 0;
		boolean[] primes = new boolean[range];
		Arrays.fill(primes, true);
		primes[0] = primes[1] = false;
		int q = (int) Math.sqrt(range);
		int i, j;
		j = 2;
		for (j = 2; j * 2 < range; j++) {
			primes[j * 2] = false;
		}

		for (i = 3; i <= q; i += 2) {
			if (!primes[i]) {
				continue;
			}
			for (j = 3; j * i < range; j += 2) {
				primes[j * i] = false;
			}
		}
		for (i = 2; i < range; i++) {
			if (primes[i]) {
				sum += i;
			}
		}
		return sum;
	}

	/*
	 * sum: 24739512092254535 time:15079 ms
	 */
	public static long primeSum_1(final int range) {
		long sum = 0;
		boolean[] primes = new boolean[range];
		Arrays.fill(primes, true);
		primes[0] = primes[1] = false;
		int q = (int) Math.sqrt(range);
		int i, j;
		for (i = 2; i <= q; i++) {
			if (!primes[i]) {
				continue;
			}
			for (j = 2; j * i < range; j++) {
				primes[j * i] = false;
			}
		}
		for (i = 2; i < range; i++) {
			if (primes[i]) {
				sum += i;
			}
		}
		return sum;
	}

}

